import UIKit

func insertionSort(_ array: inout [Int]) {
  let n = array.count
  for i in 1 ..< n {
    let current = array[i] // 当前要插入的元素
    var preIndex = i - 1 // 已排序部分的最后一个元素的索引

    // 移动已排序部分中比 key 大的元素
    while preIndex >= 0 && array[preIndex] > current {
      array[preIndex + 1] = array[preIndex] // 后移元素
      preIndex -= 1 // 移动到前一个元素
    }
    // 将 current 插入到合适的位置
    array[preIndex + 1] = current
  }
}

// 示例使用
var numbers = [5, 2, 4, 6, 1, 3]
insertionSort(&numbers)
print(numbers) // 输出: [1, 2, 3, 4, 5, 6]
